from queue import PriorityQueue

graph = {
    'A': {'B': 1, 'C': 3},
    'B': {'D': 3, 'E': 1},
    'C': {'F': 5},
    'D': {},
    'E': {'F': 1},
    'F': {}
}

heuristic = {
    'A': 5,
    'B': 4,
    'C': 2,
    'D': 6,
    'E': 1,
    'F': 0
}

def a_star(start, goal):

    pq = PriorityQueue()
    pq.put((0, start))

    g_cost = {start: 0}
    parent = {start: None}

    while not pq.empty():

        _, current = pq.get()

        if current == goal:

            path = []

            while current:
                path.append(current)
                current = parent[current]

            return path[::-1]

        for neighbor, cost in graph[current].items():

            new_cost = g_cost[current] + cost

            if neighbor not in g_cost or new_cost < g_cost[neighbor]:

                g_cost[neighbor] = new_cost

                f_cost = new_cost + heuristic[neighbor]

                pq.put((f_cost, neighbor))

                parent[neighbor] = current

result = a_star('A', 'F')

print("Shortest Path:")
print(result)